For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
2answers
59 views

Trinomial Theorem for negative exponents

I just learned of binomial theorem for negative integers (or in that case any real $n$). Does such a theorem exist for the trinomial theorem $$(a+b+c)^n$$ and has there been work done? I would think ...
2
votes
1answer
70 views

A game with rice

You have $N$ rices, and K places. You can put or take a rice in place numbered $1$ at any time. You can put a rice or take a rice from a place numbered $i$ iff there is a rice at a place $i-1$. For ...
0
votes
1answer
35 views

Ordering People

How many ways are there to order $3$ boys and $3$ girls when the girls sit together and same for the boys. How many ways are there to order $3$ boys and $3$ girls when $2$ boys can not sit ...
2
votes
2answers
82 views

The value of ${\sum_{k=0}^{20}}(-1)^k\binom{30}{k}\binom{30}{k+10}$

$\newcommand{\b}[1]{\left(#1\right)} \newcommand{\c}[1]{{}^{30}{\mathbb C}_{#1}} \newcommand{\r}[1]{\frac1{x^{#1}}}$ The value of $$\sum_{k=0}^{20}(-1)^k\binom{30}{k}\binom{30}{k+10}$$ It is also the ...
1
vote
0answers
23 views

Combinatorics while drawing cards

He have a deck with $52$ cards and $4$ suits, $H$,$D$,$C$,$S$, from which you take $26$ cards. There are some combinations that, when taken with the same suit, give a prize. Let's those combinations ...
1
vote
3answers
39 views

Proving some identities in Derangements.

Let $D_n$ denote the number of derangements of {1,2,3,...,n}. We know that for $n\geq1$, we have: \begin{equation*} D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}+...+(-1)^n\frac{1}{n!}). \end{equation*} Given ...
1
vote
1answer
25 views

How does the Borda count work?

I was watching this video. about ranking a bunch of proposals by dividing the full list in to sub lists and each person that submitted the proposals gets one of these sub-lists and ranks it. The lists ...
1
vote
0answers
34 views

Burnside Lemma's on a $2 \times 2 \times 2$ cube.

Assume you have eight $1 \times 1 \times 1$ cubes, each of different colours in which you can make a $2 \times 2 \times 2$ cube. How many unique combinations are possible without rotation symmetry, ...
2
votes
1answer
58 views

Covering a rectangle of size $n\times1$ with dominos

A rectangle of size $n\times1$ is given. (a) In how many ways the rectangle can be covered with dominoes of size $1\times1$ and $2\times1$? (b) In how many ways the rectangle can be covered with ...
0
votes
2answers
35 views

Solutions With Non-Negative Elements

I have understood the formula for the number of solutions in the positive integers of the equation $$x_1 + x_2 + \cdots + x_r = n$$ which is $${n-1 \choose r-1}$$ It can be looked at as the way to ...
0
votes
1answer
44 views

How long would it take to guess a correct card from a deck two times in a row?

How long would it take to guess a correct card two times in a row? Let's say I have a choice to make, call it A, B, C, D, E. Let's say I decide to let fortune pick for me. I take a deck of cards ...
2
votes
0answers
46 views

Total number of combinations with exclusions

I never made it out of grade $8$ math and I feel silly asking something that seems so basic so please bear with me. I want to calculate the total number of possible combinations of a set of numbers ...
0
votes
1answer
22 views

Combination With Limitations

I have read the following example from Sheldon Ross book: Consider a set of n antennas of which m are defective and n − m are functional and assume that all of the defectives and all of the ...
0
votes
1answer
33 views

Not sure what kind of sequence this would be.

Not a mathematician by any stretch, so I am not even sure where to begin to ask this question. I can logic out the answer, but I would like to know the math behind it, so here it goes... I have a box ...
0
votes
0answers
22 views

Number Partitioning of summands

So, I need to partition the number 133 in 1, 2 and 3. Like $$133 = 128*1 + 1*2 + 1*3$$ $$133 = 126*1 + 2*2 + 1*3$$ $$133 = 125*1 + 1*2 + 2*3$$ Where I always must use at least one 1, 2 or 3. I ...
5
votes
5answers
85 views

How many bit strings of length $12$ have a substring $01$?

My question is should it be $11C2$ or should it be $11C1$? Since $01$ are connected together, I take them as a single unit and there are $11$ different positions where they can be placed. Is the ...
1
vote
1answer
27 views

When will this sequence have the following limit?

For the sequence $a_0, a_1,...$ we have: $a_n = 4a_{n-1}-4a_{n-2}, a_0= 1, a_1=x$. How should we choose $x$ in order to make the sequence's limit $-\infty$, if $n \rightarrow \infty$? My idea: I ...
3
votes
1answer
49 views

On the number of ways to make $50n$ cents out of pennies, nickels, dimes and quarters

Let $f(n)$ be the number of ways to make n cents out of pennies, nickels, dimes and quarters (1c, 5c, 10c, 25c). Prove that $f(50n) = an^3 + bn^2 + cn + 1$ for some constants $a, b, c.$ I have found ...
6
votes
2answers
80 views

${n}\choose {r}$ =$ 8$ Is there any way to find such $n$ and $r$?

Let ${n} \choose {r}$ = $8$. Is there any other choice of $n$ and $r$ except $8$ and $1$, $8$ and $7$ ? In general how to check that existence is guaranteed or not?
0
votes
2answers
28 views

Permutation and Combination 3 [closed]

Four different items have to be placed in three different boxes. In how many ways can it be done such that any box can have any number of items?
0
votes
1answer
38 views

Splitting $10$ objects in three groups of sizes $4$, $4$, and $2$ [closed]

In how many ways can $10$ objects be split into three groups containing $4$, $4$, and $2$ objects?
3
votes
3answers
52 views

Pigeonhole principle proof in combinatorics

Consider the following problem: A politician gives speeches over $50$ days, each day he gives at least $1$ speech. Over the $50$ days he gives no more than $75$ speeches. Prove that there is a subset ...
5
votes
3answers
72 views

Counting the tiles in the game Tsuro

I'd like to count the number of Tsuro game tiles. In the game, a tile is a square with two points on each side where each point is connected to exactly one other point (no point connects to itself). ...
4
votes
1answer
38 views

Problem with black and white balls

You are given $b+w$ boxes, $b,w$ of them contain a black or white ball inside, respectively. You want to find a pair of boxes with both balls black ($b\geq 2$). At each trial you make a guess of 2 ...
5
votes
1answer
52 views

Partition onto subsets at the same sum

Positive integers $ a_1, a_2,\ldots, a_n $ such that $ a_k\leq k $ and the sum of all these numbers is even and equal to $ 2S $. Prove that the number can be divided into two groups, the amount of ...
0
votes
1answer
26 views

Constructing $\lambda$-difference sets. Please help.

Given a set say $A=${$0,1,4,16,r$} which is a subset of $\mathbb{Z}_{21}$. How do I find r, such that $A$ is a $\lambda$-difference set for some $\lambda$? Is there some methodical way to solve ...
1
vote
1answer
21 views

Delannoy path problem

Let $f(m,n)$ be the number of paths from $(0,0)$ to $(m,n)\in \mathbb{N}\times \mathbb{N}$, where each step is of the form $(1,0)$, $(0,1)$, or $(1,1)$. a) Show that $\sum_{m\geq 0}\sum_{n\geq 0} ...
2
votes
0answers
19 views

Combinatory: how many differents queues are possible… [duplicate]

Problem: $50$ people go to teather. The price of the ticket is $5$\$. $25$ of these people have only a $5$\$ note in their wallet, while the other $25$ only have a $10$\$ banknote. The cashier ...
2
votes
1answer
69 views

MOSP $2002$ Combinatorics Problem

I only want a hint(I already have the solution near me, but the book doesn't give a hint (MOSP) Assume that each of the $30$ MOPpers has exactly one favorite chess variant and exactly one ...
1
vote
2answers
38 views

Number of Partitions proof

How do I prove that the # of partitions of n into at most k parts equals the # of partitions of n+k into exactly k parts? I was trying to improve my ability of bijective-proofs, unfortunately I was ...
2
votes
1answer
47 views

Number of paths that lie under the diagonal

Consider a grid in $\mathbb{N}_0^2$. We can draw a path in it by traveling from point to point via a horizontal line segment to the right or vertical line segment going up. Let $k,n \in \mathbb{N}$ ...
11
votes
8answers
3k views

How many ways can $133$ be written as sum of only $1s$ and $2s$

Since last week I have been working on a way, how to sum $1$ and $2$ to have $133$. So for instance we can have $133$ $1s$ or $61$ $s$2 and one and so on. Looking back to the example: if we sum: $1 + ...
0
votes
1answer
26 views

A property of permutation codes

For $k\ge2$ and $M\ge k+2$ two integers, a permutation code matrix $C$ is a $\binom Mk\times M$ matrix which columns contain all distinct permutations of $M-k$ zeroes and $k$ ones. Page 44 of his ...
1
vote
1answer
44 views

Number of “rising/increasing sets”?

I have the following problem to solve: a) was pretty easy to show, but I am struggling to count the sequences in b. So far I noticed the obvious: $$|T_{i}|\geq i$$ Counting the sequences leads to a ...
3
votes
1answer
39 views

Set of positive integers with unique sums

What I'm looking for is the name of a type of number set. Given a number T (for total) and a set of positive integers S, I want to uniquely identify the subset of S that sums to T. All sets containing ...
1
vote
0answers
15 views

Start to Proof of bernoulli polynomials and sums

I need help starting this proof: For all integers k,l,m>=0 and not all equal to 0, (3.7) It says that that comparing the above equation (3.7) with the one discussed earlier in the paper(3.6) (shown ...
0
votes
1answer
52 views

Solutions of the Pell-type equation $x^2-2y^2=-1$

I am assigned to find solutions to the Pell-type equation $x^2-2y^2=-1$. So far, I only have $(7,5), (41,29)$ and $(239,169)$. My question is, is there a general formula to find all its solutions? ...
3
votes
2answers
80 views

How to populate a $0-$line with $1$'s?

I have a line of $n$ $0$'s like this: Zeroth index -->$000...000$ I want to populate the line with $m$ $1$'s with the following rules: (1) They have to occur after the index ...
2
votes
0answers
28 views

How to find the power of generator defined over finite field , $\mathbb F_{2 ^m}$?

List item Actually ,I am trying to execute the algorithm to find the power of generator of field(group) as shown in table of attached file but when k=7 and onward ,I could not understand what is ...
0
votes
0answers
31 views

Conditional Probability about drawing cards.

Let's have a stack of 52 cards, from which we'll take 26 cards (order doesn't matter) We can win bet $H$ if any (it could be also, more than one) of several card combinations is present on the cards ...
1
vote
0answers
15 views

Book recommendation on integer programming ? (in order to solve a set cover problem)

I'm trying to solve a set cover problem. To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and ...
2
votes
3answers
47 views

Probability of choosing subsets $A$, $B$ such that $A\cap \!\,B=\varnothing \!\,$ and $A\cup \!\,B=X$

I'm given a set $X={\{\ \!\,1,2,3,...,n\!\ \}} $, and I have to calculate the probability that, for two randomly chosen, different, non-empty sets $A, B$: $A,B\subseteq \!\,X$, we have $A\cap ...
0
votes
0answers
28 views

Possible areas within an integer grid

Given a 1x1 grid with 4 lattice points $[(0,0),(0,1),(1,0),(1,1)]$ (equivalent to a $2 \times 2$ grid of vertices), there are 2 shapes and areas that can be formed: a triangle and a square. There are ...
0
votes
1answer
17 views

Combining an outcome of a score

Hey I was wondering how many are the possibilities of combining the scored points of a result such $133:75$ from a basketball game? Considering that there are fouls($1$ point), normal($2$ points) and ...
0
votes
0answers
21 views

1 and multiplication form a group - Meaning?

I heard someone say this with respect to combinatorial mathematics, but I have no idea what they mean? Any ideas?
2
votes
2answers
57 views

A problem on pigeonhole principle

Following is a problem, which makes use of the pigeonhole principle. But How? "Let $A$ be a set of $n$ integers. Prove that $A$ contains a subset such that the sum of its elements is divisible by ...
0
votes
0answers
25 views

Number of permutations in a multiset

How many permutations of the multiset {$1^{a_{1}},2^{a_{2}},...,n^{a_{n}}$} have no $1$s placed consecutively? What inequality has to hold in order for there to be such permutations? What I have: ...
2
votes
1answer
26 views

Partitioning of Teams

In how many ways can we partition $2n$ people into $n$ teams with different names of two people each and assign to each team who plays position $A$ and who plays position $B$? (For instance, the ...
0
votes
1answer
43 views

Counting problem for seating in a circle

I am having a hard time understanding the answer to the following problem from Grimaldi: "At Professor Alfred's science camp, 17 students have lunch together each day at a circular table. They are ...
2
votes
2answers
66 views

find coefficient of $x^{50}$

Let $f(x)=\frac{1}{(1+x)(1+x^2)(1+x^4)}$then find the coefficient of term $x^{50}$ in $(f(x))^3$.I think that we can set $$(f(x))^3=\frac{a}{(1+x)^3}+\frac{b}{(1+x^2)^3}+\frac{c}{(1+x^4)^3}$$ and find ...