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. Combinatorics is a ...

learn more… | top users | synonyms (4)

5
votes
3answers
937 views

The number of subsets of a set of cardinality $n$

Please help with this question. Show that for a finite set $A$ of cardinality $n$, the cardinality of P(A) is $2^n$, where $P(A)$ is the power set of $A$. Thank you in advance for any help that is ...
4
votes
2answers
316 views

A Combinatorial proof for the identity $\sum_i \sum_j \min(i,j) = \sum_k k^2$

I have to prove this (a combinatorally proof, counting a set in two different ways): $$\sum_{i=1}^n\sum_{j=1}^n\mathrm{min}(i,j)=\sum_{k=1}^nk^2 .$$ This is what I have done: take the set ...
4
votes
1answer
65 views

Value of $k$ satisfying this condition

In a pile you have 100 stones. A partition of the pile in $k$ piles is good if: 1) the small piles have different numbers of stones; 2) for any partition of one of the small piles in 2 smaller ...
0
votes
1answer
161 views

Is my argument wrong? (A combinatorial exercise)

How many ways are there to arrange $m$ distinct flags on a row of $r$ flagpoles? The order of the flags on the flagpoles (from top to bottom) matters. My argument is: I have $mr$ points and I have to ...
1
vote
1answer
83 views

A “fast” approach to compute $\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$ [duplicate]

Possible Duplicate: How to find a closed formula for the given summation I am looking for a fast/best approach to compute $$\sum_{i=0}^{n} \binom{19}{i} \times \binom{7}{n-i}$$ For ...
2
votes
1answer
262 views

Optimizing a string to have the shortest possible unique substrings

I would like to construct a length $N$ string over a $k$-letter alphabet, $S$, such that any substring of $P$ sequential characters in $S$ is unique for as small a value of $P$ as possible. To ...
1
vote
3answers
500 views

Finding characteristic equation of problem and solve recurrence relation

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers ...
3
votes
1answer
192 views

Counting fractions with $n$ digits in the numerator and denominator

Playing around with fractions, I eventually had to consider the following question: Is there a formula for counting how many proper fractions in lowest terms with $n$ base-$b$ digits in both the ...
3
votes
3answers
81 views

How can I compute this expression?

I have to understand what is this expression $\sum_{A\subset[n]}\prod_{i\in A}1/i$ where $[n]=\{1,\ldots,n\}$. And then prove it. I was using a very complicated method to understand what this ...
8
votes
5answers
258 views

finding the coefficient of $x^{14}$ in the expression: $\frac{5x^2-x^4}{(1-x)^3}$

I have a homework question which requires me to find the coefficient of $x^{14}$ in the expression: $\dfrac{5x^2-x^4}{(1-x)^3}$ I have not figured out a way to do this (I believe this is because my ...
19
votes
3answers
471 views

Getting the name of combinatorial problems

I'll often find myself with some combinatorial problem that's obviously been studied before. For example, "Find the smallest set(s) of positive integers such that every integer from 1 to n is the sum ...
5
votes
1answer
375 views

Restricted Integer Compositions

Let $c_{k}(N;[a,b])$ denote the number of compositions of $N$ into $k$ parts, where each part is restricted to the interval $[a,b]$, i.e., $N = \sum_{i = 1}^{k} s_{i}$ with $a \leq s_{i} \leq b$. The ...
2
votes
1answer
123 views

Coming up with a generating function

I have a homework assignment which is to write a Generating Function of the following problem: "There are $n$ identical boxes , there are $3$ different rooms in which they can be put. Each room can ...
15
votes
3answers
628 views

Finding when $(a-n)(b-n)|(ab-n)$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n ...
3
votes
3answers
762 views

What are the symmetries of the tetrahedron?

Suppose I like combinatorics, and want to count how many ways to paint the faces of a tetrahedron using a pallet of $x$ colors. I don't want to over count cases where I could just rotate one painted ...
4
votes
4answers
195 views

Combinatorics | Building a wall

Let $n$ be a positive integer. A child builds a wall along a line with $n$ identical cubes. He lays the first cube on the line and at each subsequent step, he lays the next cube either on the ground ...
11
votes
3answers
209 views

Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate: $$\sum_{0\le k\le n/2}\binom{n-k}{k}$$ Any idea?
3
votes
2answers
674 views

Distributing a cake cut with four vertical slices among three people

A round cake was cut with a knife $4$ times vertically in such a way that it is cut to maximum number of pieces.Find the number of ways of distributing these cakes among three people such that ...
3
votes
3answers
846 views

Truth table, clarification of $2^n$ row rule?

My question is about truth tables and specifically why there is $2^n$ rows for $n$ inputs in a truth table? I understand that there's a finite amount of states a variable can be in, here it's 2 - ...
2
votes
1answer
165 views

Bound for multi-index sum

I have difficulties in evaluating the multi-index notation in the following context: Let $x \in R^n$ and let $i$ be a multi-index, $i=(i_1, \dots, i_n)$. Now I want to know the bound of the sum ...
3
votes
2answers
165 views

What is a simple expression for $\sum\limits^m_{j=1}(m-j)2^{j-1}$ and a combinatorial interpretation of it?

$$f(m)=\sum^m_{j=1}(m-j)2^{j-1}$$ I've to understand what is a simple form of $f$ by computing some value of it, but I can't see a simple form of it, can anyone help me? I have also to give a ...
5
votes
2answers
164 views

How to count possible separations of N items into K clusters?

How many ways are to separate N same items into K clusters. For N=10, K=4 are there 9 ways: (7,1,1,1), (6,2,1,1), ...
5
votes
1answer
261 views

What's the difference between Ramsey theory and Extremal graph theory?

Wikipedia teaches us that problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?" It ...
0
votes
1answer
143 views

In how many ways can some or all of the $5$ distinct coins be put into $8$ pockets?

In how many ways can some or all of the $5$ distinct coins be put into $8$ pockets? Could this be modeled as the problem of "In how many ways N distinct items be put into r distint groups ...
3
votes
1answer
67 views

what's the most probable min interval in 100 balls in a circle?

I have $n=100$ balls, in which $h=3$ are red, 97 are blue. I randomly place the balls in a circle, then check the minimum interval of red balls (e.g., if 2 red balls are consecutive, then their ...
19
votes
2answers
837 views

Combinatorial proof of $\binom{3n}{n} \frac{2}{3n-1}$ as the answer to a coin-flipping problem

In the recent question "What's the probability that a sequence of coin flips never has twice as many heads as tails?" I argue in my answer that the number of ways $S(n)$ to obtain twice as many heads ...
1
vote
1answer
63 views

How many ways does the following tasks can be accomplished?

There are seven tasks $(1,2,3,4,5,6,7)$ which have to done by seven people $(A,B,C,D,E,F$ and $G)$.Each person can do only one task. Task $1$ must be done by $A,B$ or $C$.Task $4$ and $5$ ...
7
votes
6answers
245 views

Finding the minimum number of students

There are $p$ committees in a class (where $p \ge 5$), each consisting of $q$ members (where $q \ge 6$).No two committees are allowed to have more than 1 student in common. What is the minimum and ...
2
votes
0answers
107 views

What does it mean if a sequence is indexed beyond its bounds?

I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences. Part of the algorithm involves ...
1
vote
1answer
215 views

Simple combinatorics - tiling shapes with dominoes

I remember a long time ago during my university entrance interview I was asked a deceptively simple combinatorics (or what I believe to be combinatorics) question. Imagine you had a rectangle of size ...
1
vote
1answer
487 views

Lucas' Theorem and Pascal's Triangle

I have a general question about Lucas' Theorem. Lucas' Theorem says the following: Theorem (Lucas' Theorem) Let $p$ be a prime number. Write $n$ and $k$ in base $p$: $n = a_0 + a_{1}+a_{2}p^{2} + ...
5
votes
2answers
525 views

Number of positive integral solutions for $ab + cd = a + b + c + d $ with $1 \le a \le b \le c \le d$

How many positive integral solutions exist for: $ab + cd = a + b + c + d $,where $1 \le a \le b \le c \le d$ ? I need some ideas for how to approach this problem.
7
votes
2answers
5k views

Finding the n-th lexicographic permutation of a string

I have an ordered set of symbols S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. I want to find the 1,000,000-th permutation in lexicographic order of S. It is a programming puzzle, but I wanted to figure out a ...
1
vote
1answer
203 views

In how many ways can $10$ letters be placed in $10$ addressed envelope such that exactly $9$ letters are in correct envelope?

I have one problem which goes like this: "In how many ways can $10$ letters be placed in $10$ addressed envelope such that exactly $9$ letters are in correct envelope?" If I understand the problem ...
1
vote
2answers
588 views

Prove König's theorem using Dilworth's theorem

I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then ...
5
votes
3answers
172 views

Number of cells intersecting the line segment joining $(0,0)$ and $(m,n)$

If $m,n \in \mathbb{N}$ . Let $g(m, n)$ be the number of cells that the line joining $(m, n)$ to $(0, 0)$ cuts in the region $0 \le x \le m$ and $0 \le y ≤ n$. For example $g(1, 1)$ is ...
5
votes
2answers
165 views

Probability for rearranging balls in particular order

Given $N$ boxes, each containing one ball each say numbered as $B_1, B_2, B_3, \ldots, B_N$. We take all of these balls out and put them back in different boxes but not their original one. So, $B_1$ ...
2
votes
4answers
367 views

How to derive a general formula for this problem? (pairs of people seated around a table)

$N$ people attend a dinner party and sit round a circular table.Each person knows only the people sitting immediately next to him and has to be introduced to everyone else.If the total number ...
3
votes
2answers
154 views

2009 cards | combinatorics

Consider 2009 cards which are lying in sequence on a table. Initially, all cards have their top face white and bottom face black. The cards are enumerated from 1 to 2009. Two players, Amir and Ercole, ...
6
votes
3answers
114 views

Numbering students inequality problem

Ten students are sitting around a campfire. A teacher randomly assigns each student a different number from 1-10. Another teacher assigns a new number to each student with the requirement that the new ...
5
votes
2answers
198 views

On a property of the binomial coefficient

Let $n$ be a positive integer and $p$ a prime, how can I prove that the highest power of $p$ that divides $\binom{2n}{n}$ is exactly the number of $k\geq1$ such that $\lfloor 2n/p^k\rfloor$ is odd?
2
votes
4answers
105 views

How to “efficiently” compute the number of solution of $25x= 5y+8z$ such that $x,y,z \in [0,9]$ and $x,y,z \in \mathbb{W}$?

The mother problem: Find the sum of all $3$ digit numbers which are equal to $25$ times the sum of their digits. So we can write: $$\begin{align} 100x+10y+z &= 25 ...
2
votes
2answers
4k views

How many ways can 10 teachers be divided among 5 schools?

In how many ways can ten teachers be divided among five schools? One answer is that each teacher can go to any of the five schools so there are $10^5$ possibilities. However, if you treat each ...
3
votes
2answers
124 views

A combinatorial exercise

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars. This is what I have done, but I realized that it's ...
2
votes
2answers
279 views

Partition of a set [duplicate]

Possible Duplicate: Number of equivalence relations splitting set into sets with exactly 3 elements Given a set $S$ ($|S|$ even), I'm looking for the number of partitions of $S$, so that ...
1
vote
1answer
208 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
5
votes
1answer
87 views

References for analogues of chromatic polynomials where colorings which differ only by permutation of colors are counted as the same

It's well-known that chromatic polynomials count colorings which differ by permutations of colors. What is known about their analogues which don't count such colorings as distinct?
36
votes
4answers
5k views

Probability for the length of the longest run in $n$ Bernoulli trials

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, ...
1
vote
4answers
238 views

How many ways to form a committee, subject to certain restrictions?

From among six couples, a committee of $5$ members is to be formed. If the selected committee has no couple, then in how many ways can the committee be formed? My approach is to count things ...
9
votes
2answers
343 views

Proportion of spanning trees in a network in a social media messaging context

Consider a graph, such as the following: I'm considering a model of message propagation (e.g. re-tweeting) in this network, starting from a root node (e.g. the node 1 in the lower-left). ...